# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        ppath=[]
        qpath=[]
        def findnode(node,target,path):
            path.append(node.val)
            if node.val==target.val:
                return 
            elif node.val>target.val:
                findnode(node.left,target,path)
            else:
                findnode(node.right,target,path)
        findnode(root,p,ppath)
        findnode(root,q,qpath)
        index=0
        pre=ppath[0]
        print(ppath)
        print(qpath)
        while index<min([len(ppath),len(qpath)]):
            if ppath[index]!=qpath[index]:
                return TreeNode(pre)
            else:
                pre=ppath[index]
                index+=1
        return TreeNode(ppath[index-1])
